package class02;

import java.util.HashMap;

/*
 * 题目描述：
 * 一条消息有编号和信息内容两部分组成，编号从1开始依次排列。
 * 现在有一个消息接收和打印的系统，它能够接收任意顺序的消息，但要求按编号从小到大的顺序打印。
 * 例如：先接收消息编号为2、4、1、3，但要按1、2、3、4的顺序打印。
 * 
 * 系统设计要求：
 * 1. 消息可以按任意顺序接收
 * 2. 当接收到的消息能连接成从1开始的连续序列时，立即打印该连续序列
 * 3. 使用链表和哈希表实现高效的消息缓存和连接
 * 
 * 实现思路：
 * 1. 使用两个HashMap分别维护每个连续区间的头部和尾部节点
 * 2. 当接收一个消息时，尝试将其与相邻区间连接形成更大的连续区间
 * 3. 如果连接后能形成从1开始的连续序列，则立即打印
 * 4. 通过waitPoint变量记录下一个期望接收并打印的消息编号
 */
public class Code03_ReceiveAndPrintOrderLine {

	public static class Node {
		public String info;
		public Node next;

		public Node(String str) {
			info = str;
		}
	}

	public static class MessageBox {
		private HashMap<Integer, Node> headMap;
		private HashMap<Integer, Node> tailMap;
		private int waitPoint;

		public MessageBox() {
			headMap = new HashMap<Integer, Node>();
			tailMap = new HashMap<Integer, Node>();
			waitPoint = 1;
		}

		// 消息的编号，info消息的内容, 消息一定从1开始
		public void receive(int num, String info) {
			if (num < 1) {
				return;
			}
			Node cur = new Node(info);
			// num~num
			headMap.put(num, cur);
			tailMap.put(num, cur);
			// 建立了num~num这个连续区间的头和尾
			// 查询有没有某个连续区间以num-1结尾
			if (tailMap.containsKey(num - 1)) {
				// 如果有以num-1结尾的区间，将该区间的尾部连接到当前节点
				tailMap.get(num - 1).next = cur;
				// 移除以num-1结尾的记录，因为它不再是任何区间的尾部
				tailMap.remove(num - 1);
				// 移除以num开始的记录，因为当前节点已连接到前一个区间
				headMap.remove(num);
			}
			// 查询有没有某个连续区间以num+1开头的
			if (headMap.containsKey(num + 1)) {
				// 如果有以num+1开头的区间，将当前节点连接到该区间头部
				cur.next = headMap.get(num + 1);
				// 移除以num结尾的记录，因为它不再是独立区间的尾部
				tailMap.remove(num);
				// 移除以num+1开始的记录，因为它不再是独立区间的头部
				headMap.remove(num + 1);
			}
			// 如果当前收到的消息编号正是等待打印的编号，则触发打印
			if (num == waitPoint) {
				print();
			}
		}

		private void print() {
			// 获取从waitPoint开始的第一个节点
			Node node = headMap.get(waitPoint);
			// 移除已经处理过的头部映射
			headMap.remove(waitPoint);
			// 遍历并打印连续的消息节点
			while (node != null) {
				System.out.print(node.info + " ");
				node = node.next;
				// 更新等待点，表示下一条应该接收的消息编号
				waitPoint++;
			}
			// 移除已经处理过的尾部映射
			tailMap.remove(waitPoint-1);
			System.out.println();
		}

	}

	public static void main(String[] args) {
		// MessageBox only receive 1~N
		MessageBox box = new MessageBox();
		// 1....
		System.out.println("这是2来到的时候");
		box.receive(2,"B"); // - 2"
		System.out.println("这是1来到的时候");
		box.receive(1,"A"); // 1 2 -> print, trigger is 1
		box.receive(4,"D"); // - 4
		box.receive(5,"E"); // - 4 5
		box.receive(7,"G"); // - 4 5 - 7
		box.receive(8,"H"); // - 4 5 - 7 8
		box.receive(6,"F"); // - 4 5 6 7 8
		box.receive(3,"C"); // 3 4 5 6 7 8 -> print, trigger is 3
		box.receive(9,"I"); // 9 -> print, trigger is 9
		box.receive(10,"J"); // 10 -> print, trigger is 10
		box.receive(12,"L"); // - 12
		box.receive(13,"M"); // - 12 13
		box.receive(11,"K"); // 11 12 13 -> print, trigger is 11

	}
}